#
# Created by Administrator on 2021/7/29 AT 9:24.
#
# 物品编号：1 2 3 4
# 体积：   2 3 4 5
# 价值：   3 4 5 6
# 背包容量：8

import time


def package(m, n, volume, value):
    """
    :param m:  物品个数
    :param n:  背包容量
    :param volume:  每个物品的体积
    :param value:   每个物品的价值
    :return:
    转移方程：
    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volume[i]] + value[i])
    压缩：
    遍历背包时逆向推，用上一条的旧数据
    dp[j] = max(dp[j],dp[j-w[i]]+c[i])
    """
    dp = [[0] * (1 + n) for _ in range(m + 1)]  # dp矩阵 注意维数都+1
    # 遍历物品
    for i in range(1, m + 1):
        # 遍历背包容量
        for j in range(1, n + 1):
            if volume[i - 1] > j:  # 物品体积大于背包容量
                dp[i][j] = dp[i - 1][j]  # 不能放入背包，最大价值等于同等容量背包，考虑前i-1个物品
            else:
                # 如果这个物品能放入背包，那么：
                # 1、放这个物品   总价值为该物品的价值 + （背包容积减去该物品体积，考虑前i-1个物品时的最大价值）
                # 2、不放这个物品
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volume[i - 1]] + value[i - 1])
    print(dp)
    return dp[m][n]


def package_rooling(m, n, volume, value):
    """
    滚动数组
    每一行只与上一行有关
    :param m:  物品个数
    :param n:  背包容量
    :param volume:  每个物品的体积
    :param value:   每个物品的价值
    :return:
    """
    dp = [0] * (1 + n)  # dp矩阵 注意维数都+1
    # 遍历物品
    for i in range(m):
        # 遍历背包容量  从后往前
        for j in range(n, -1, -1):
            if j >= volume[i]:
                dp[j] = max(dp[j], dp[j - volume[i]] + value[i])

        print(dp)
    return dp[n]


if __name__ == '__main__':
    print(package(4, 8, [2, 3, 4, 5], [3, 4, 5, 6]))
    print(package_rooling(4, 8, [2, 3, 4, 5], [3, 4, 5, 6]))

